Codeforces Round #823 (Div. 2)

A

弱智题，对于每一个轨道会花费 $\min\{a_i,c\}$ 的代价，直接累加即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

int n, c, T, ans, a[N], cnt[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        memset(cnt, 0, sizeof(cnt));
        cin >> n >> c;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            cnt[a[i]]++;
        }
        ans = 0;
        for (int i = 1; i <= 100; i++) {
            if (!cnt[i]) continue;
            if (cnt[i] >= c) ans += c;
            else ans += cnt[i];
        }
        cout << ans << endl;
    }
}

B

如果没有 $t$ 的限制，那就是一个求 $\min\limits_{i=1}^n |x-x_i|$ 的简单题目，直接取最大值和最小值的算术平均即可。

现在考虑加入 $t$ 的贡献。我们把 $x_i$ 变为 $x_i+t_i$ 和 $x_i-t_i$ 两个点，把问题转化为上面的问题。容易证明这对最后的答案没有影响。

注意 cin/cout 输出浮点数会有科学计数法的问题，需要特判奇数。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int x[N], t[N], n, T, mx, mn;

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        memset(x, 0, sizeof(x));
        memset(t, 0, sizeof(t));
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> x[i];
        mx = -1e9, mn = 1e9;
        for (int i = 1; i <= n; i++) {
            cin >> t[i];
            mx = max(mx, max(x[i] + t[i], x[i] - t[i]));
            mn = min(mn, min(x[i] + t[i], x[i] - t[i]));
        }
        cout << (mx + mn) / 2;
        if ((mx + mn) & 1) cout << ".5";
        cout << endl;
    }
}

C

一个1200的题楞是不会做

维护后缀最小值 $mn_i$ ，在第 $i$ 位上，最优情况可以把 $0$ 至 $mn_i-1$ 的每一种字符全都插入进来。如果 $s_i=mn_i$ 则选择保留 $s_i$ ，否则执行操作拿掉这一个字符。

时间复杂度 $O(10n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int a[N], suf[N], cnt[N], n, T;
string s, ans;

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        memset(cnt, 0, sizeof(cnt));
        cin >> s;
        n = (int)s.size();
        for (int i = 0; i < n; i++) a[i] = s[i] - '0';
        suf[n] = 9;
        for (int i = n - 1; i >= 0; i--) suf[i] = min(suf[i + 1], a[i]);
        ans = "";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < suf[i]; j++)
                while (cnt[j]) {
                    cnt[j]--;
                    ans += char(j + '0');
                }
            if (s[i] - '0' == suf[i]) ans += s[i];
            else cnt[min(a[i] + 1, 9)]++;
        }
        for (int i = 0; i < 10; i++)
            while (cnt[i]) {
                cnt[i]--;
                ans += char(i + '0');
            }
        cout << ans << endl;
    }
}

D

很有意思的题目。

我们可以把两个字符串内相对的字符换到任意一个地方，并且依然保持相对关系。于是考虑把 $b$ 反转，转化为把 $a$ 和 $b'$ 的任何位置上的一个字符换到相同的位置上。

我们组出 $n$ 个无序字符对 $(a_i,\,b_{n-i+1})$ ，只有能够将这些字符对组成回文串时，才能满足要求。

时间复杂度 $O(n\log{n})$ 。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

string s1, s2;
int n, T, cnt, palin, a[N], b[N];

set<pair<int, int> > st;
map<pair<int, int>, int> mp;

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> s1 >> s2;
        for (int i = 1; i <= n; i++) {
            a[i] = s1[i - 1] - 'a';
            b[i] = s2[i - 1] - 'a';
        }
        st.clear(), mp.clear();
        cnt = palin = 0;
        for (int i = 1; i <= n; i++) {
            auto p = make_pair(a[i], b[n - i + 1]);
            if (p.first > p.second) p = {p.second, p.first};
            if (st.count(p)) {
                mp[p]++;
                cnt += (mp[p] & 1) ? 1 : -1;
                if (p.first == p.second) palin += (mp[p] & 1) ? 1 : -1;
            } else {
                mp[p] = 1;
                st.insert(p);
                cnt++;
                if (p.first == p.second) palin++;
            }
        }
        if (cnt == palin && n % 2 == palin) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

E

待补。

F

待补。